package src.java.medium;

/**
 * @author 袁敏
 * @className Solution96
 * @date 2024/7/24
 * @description TODO
 */

public class Solution96 {
    public static void main(String[] args) {
        ListNode head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, null)))));
        Solution96 solution96 = new Solution96();
        ListNode newHead = solution96.reverseBetween(head, 2, 4);
    }

    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (left == right) return head;
        ListNode start = new ListNode(0, head);
        ListNode end;
        int index = 0;
        while (index < left - 1) {
            start = start.next;
            index++;
        }
        end = start;
        while (index < right) {
            end = end.next;
            index++;
        }
        ListNode tail = end.next;
        end.next = null;
        ListNode newHead = reverseList(start.next);
        start.next.next = tail;
        start.next = newHead;
        return left == 1? newHead : head;
    }

    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}